﻿// 删除链表的倒数第 N 个结点
// 
// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//
//
//示例 1：
//
//
//输入：head = [1, 2, 3, 4, 5], n = 2
//输出：[1, 2, 3, 5]
//示例 2：
//
//输入：head = [1], n = 1
//输出：[]
//示例 3：
//
//输入：head = [1, 2], n = 1
//输出：[1]
//
//
//提示：
//
//链表中结点的数目为 sz
//1 <= sz <= 30
//0 <= Node.val <= 100
//1 <= n <= sz
//

//进阶：你能尝试使用一趟扫描实现吗？

//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/remove-nth-node-from-end-of-list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//这道题的难点在于进阶做法，也就是使用一遍扫描实现。可以用“前后双指针”来解决。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    //先定义两个前后双指针，让他们都指向头结点。
    struct ListNode* front = head;
    struct ListNode* back = head;

    int count = 0;//计数，用来记录链表的长度。

    
    while (front->next != NULL) {

        //当两个指针相隔n个大小时，，两个指针同时移动。
        if (count >= n) {
            front = front->next;
            back = back->next;
            count++;
        }
        //初始先让front指针先移动，使得两个指针相隔n个大小。
        else {
            front = front->next;
            count++;
        }
    }
    //为了防止 head = [1], n = 1，head = [1, 2], n = 1，此类情况发生
    if (count == n - 1) {
        head = head->next;
    }
    //正常操作，改变指针指向以此达到删除指针的操作。
    else {
        back->next = back->next->next;
    }

    return head;
}
